/*
 * 查找最小的k个元素
 *
 * 方法：
 *     1. 快速排序的变形；
 *     2. 堆排序；
 */

#include <stdio.h>

//swap two number
int swap(int *a, int *b)
{
    int tmp = *b;
    *b = *a;
    *a = tmp;
}
//quick Sort
int find_small_member(int * array, int start, int end, int k)
{
    int i = start+1;
    int j = end;
    while (i < j) {
        while (array[i] < array[start] && i < end) i++;
        while (array[j] > array[start] && j > 0) j--;
        if (i < j) {
            swap(array+i, array+j);
        }
    }
    swap(array+start, array+j);
    if (j-start+1 == k) {
        for (int z = 0; z < k; ++z) {
            printf("%d ", array[start+z]);
        }
        printf("\n");
    }
    else if (j-start+1 > k) {
        find_small_member(array, start, j-1, k);
    }
    else {
        for (int z=start; z < j+1; ++z) {
            printf("%d ", array[z]);
        }
        find_small_member(array, j+1, end, k-j-1+start);
    }
}

int main()
{
    int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    find_small_member(array, 0, 9, 4);
}


